package com.cat.twoPointerTechnique;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-score-of-a-good-subarray/description/
 * @create 2025/8/2 15:01
 * @since JDK17
 */

public class Solution07 {
    static int N = ((int) (1e5 + 10)), t;
    static int[] stack = new int[N];
    static int[][] ans = new int[N][2];

    public int maximumScore(int[] nums, int k) {
        int res = 0, n = nums.length, cur;
        for (int i = 0; i < n; i++) {
            while (t > 0 && nums[stack[t - 1]] >= nums[i]) {
                cur = stack[--t]; // 上一次的位置
                ans[cur][0] = t == 0 ? -1 : stack[t - 1];
                ans[cur][1] = i;
            }
            stack[t++] = i;
        }
        while (t > 0) {
            cur = stack[--t];
            ans[cur][0] = t == 0 ? -1 : stack[t - 1];
            ans[cur][1] = -1;
        }
        for (int i = n - 1; i >= 0; i--) {
            if (ans[i][1] != -1 && nums[i] == nums[ans[i][1]]) {
                ans[i][1] = ans[ans[i][1]][1]; // 找到左边的
            }
        }
        for (int i = 0, l, r; i < n; i++) {
            l = ans[i][0];
            r = ans[i][1] == -1 ? n : ans[i][1];
            if (l < k && k < r) {
                res = Math.max(res, nums[i] * (r - l - 1));
            }
        }

        return res;
    }
}
